iT邦幫忙

2022 iThome 鐵人賽

DAY 28
0
自我挑戰組

Udemy課程上完你也可以開始Codewars 30天系列 第 28

[Day28] Codewars >>> Consecutive k-Primes (Python)

  • 分享至 

  • xImage
  •  

題目(5kyu):

A natural number is called k-prime if it has exactly k prime factors, counted with >multiplicity. A natural number is thus prime if and only if it is 1-prime.

Examples:
k = 2 -> 4, 6, 9, 10, 14, 15, 21, 22, …
k = 3 -> 8, 12, 18, 20, 27, 28, 30, …
k = 5 -> 32, 48, 72, 80, 108, 112, …
Task:
Given an integer k and a list arr of positive integers the function consec_kprimes (or >its variants in other languages) returns how many times in the sequence arr numbers >come up twice in a row with exactly k prime factors?

Examples:
arr = [10005, 10030, 10026, 10008, 10016, 10028, 10004]
consec_kprimes(4, arr) => 3 because 10005 and 10030 are consecutive 4-primes, 10030 and >10026 too as well as 10028 and 10004 but 10008 and 10016 are 6-primes.

consec_kprimes(4, [10175, 10185, 10180, 10197]) => 3 because 10175-10185 and 10185- >10180 and 10180-10197 are all consecutive 4-primes.

解題思路

題目理解:當一個數num擁有k個質因數,則稱num為k質因數。設計一函式代入數字k與列表arr,返還列表arr中連續出現k質因數數的次數。
關於如何找出某數所擁有的質因數,可以參考我這篇Day23提到的方法,將其改為返還質因數的數量即可。

def first_divisor(num):
    """找到正整數num的1以外最小因數並返還"""
    for n in range(2,int(num**0.5+1)):
        if num % n == 0:
            return n
    #若在根號num範圍內無法找到因數,代表num本身為質數並返還num
    return num
def kprimes(number):
    """找到正整數number所有的質因數"""
    num = number
    prime_divisor = []
    while first_divisor(num) != num:
        #將找到的最小因數加入prime_divisor並將num除去最小因數
        #因為number為所有的prime_divisor相乘,故將num不斷除去找到到質因數直到num為止
        prime_divisor.append(first_divisor(num))
        num = num/first_divisor(num)
    #則此時num為number的最後一個質因數
    prime_divisor.append(int(num))
    #最後返還質因數數量
    return len(prime_divisor)     
def consec_kprimes(k, arr):
    """找到arr中有多少組相鄰的元素為指定k質因數"""
    lst_kprime = [kprimes(num) for num in arr ]
    reslut = 0
    consec = False
    for i in lst_kprime:
        #若找到符合k條件,但consec為False,表示為第一個符合條件的數
        if i == k and consec == False:
            consec = True
            #直接進入下個循環看看下個數是否符合條件
            continue
        if i == k:
            reslut += 1
        else:
            consec = False
    return reslut

上一篇
[Day27] Codewars >>> First non-repeating character (Python)
下一篇
[Day29] Codewars >>> Weight for weight (Python)
系列文
Udemy課程上完你也可以開始Codewars 30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言